package homework.exp03;

import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.Scanner;

/**
 * 使用动态规划方法计算n条直线（无三线共点）可能形成的所有交点数量
 * 核心思想：通过递推方式，逐步构建从少到多的直线组合可能形成的交点数
 */
public class H {
    static Scanner cin = null;

    // 静态代码块，优先从文件读取输入，失败则从标准输入读取
    static {
        try {
            cin = new Scanner(new FileReader(new File("H.in")));
        } catch (IOException e) {
            cin = new Scanner(System.in);
        }
    }

    /**
     * 主函数
     * 使用动态规划预处理所有可能的交点情况，然后处理输入并输出结果
     */
    public static void main(String[] args) {
        // dp[i][j] = 1 表示i条直线可以形成j个交点
        // 数组大小设为21x200，覆盖可能的问题规模
        int[][] dp = new int[21][200];
        
        // 动态规划预处理阶段
        for (int i = 0; i < 21; i++) {
            // 初始化：i条直线全平行时，交点数为0（这是所有情况的基础）
            dp[i][0] = 1;
            
            // 遍历i条直线所有可能的交点数j
            for (int j = 0; j <= i * (i - 1) / 2; j++) {
                // 如果i条直线可以形成j个交点
                if (dp[i][j] == 1) {
                    // 尝试添加更多的平行直线，构建更大的直线集合
                    for (int r = i + 1; r < 21; r++) {
                        // k表示新添加的平行直线数量
                        int k = r - i;
                        // 关键递推式：
                        // - 新添加的k条平行直线与原有的i条直线分别相交
                        // - 新增交点数为k * i（每条新直线与i条原有直线相交）
                        // - 总交点数 = 原有j个交点 + 新增k*i个交点
                        dp[i + k][k * i + j] = 1;
                    }
                }
            }
        }

        // 处理输入并输出结果
        while (cin.hasNext()) {
            int n = cin.nextInt();
            // 输出n条直线所有可能的交点数
            // 最大可能交点数为n*(n-1)/2（所有直线两两相交）
            for (int i = 0; i <= n * (n - 1) / 2; i++) {
                if (dp[n][i] == 1) {
                    System.out.print(i + " ");
                }
            }
            System.out.println();
        }
    }
}